package developer.算法.链表.反转链表;

/**
 * @author zhangyongkang
 * @time 2024/6/12 10:29
 * @description
 */

/**
 * 1 2 3 4 5
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * 【 next】 [ next ] [ next]  [next]->
 * }
 */
public class Solution_self {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        printList(listNode);
        Solution3 solution3 = new Solution3();

        System.out.println("reverse----👇");
//        ListNode listNode1 = reverseList(listNode);
        printList(solution3.reverseList(listNode));
    }

    // 1 2 3 4 5
    static class Solution3 {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode newHead = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }

    private static void printList(ListNode node) {
        ListNode currentNode = node;
        while (currentNode != null) {
            System.out.println(currentNode.val);
            currentNode = currentNode.next;
        }
    }

    //递归版本

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;

    }

//循环版本
//    public static ListNode reverseList(ListNode head) {
//
//
//        ListNode current = head;
//        ListNode pre = null;//重点在缓存两个数据 下一个 以及上一个
//        while (current != null) {
//            ListNode next = current.next;
//
//            current.next = pre;
//            pre=current;
//            current=next;
//
//        }
//        return pre;
//    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

//    class MinCha {
//        public ListNode reverseList(ListNode head) {
//            ListNode prev = null;
//            ListNode curr = head;
//            while (curr != null) {
//                ListNode next = curr.next;
//                curr.next = prev;
//                prev = curr;
//                curr = next;
//            }
//            return prev;
//        }
//    }






